package com.cdream.basic.algorithm.leetcode.bfs;

import cn.hutool.core.collection.CollUtil;

import java.util.*;

/**
 * @author cdream
 * @date 7/10/21
 */
public class Question126 {
    private List<List<String>> res = new ArrayList<>();
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Map<String, List<String>> map = new HashMap<>();
        for (String word : wordList) {

            // 进行匹配分组
            for (int i = 0; i < word.length(); i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i + 1);
                List<String> list = map.getOrDefault(newWord, new ArrayList<>());
                list.add(word);
                map.put(newWord, list);
            }
        }

        Deque<Pair<String, List<String>>> deque = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Pair<String, List<String>> pair = new Pair<>(beginWord, new ArrayList<>(Arrays.asList(beginWord)));
        deque.add(pair);
        while (deque.size()!=0){
            Pair<String, List<String>> poll = deque.poll();
            List<String> level = poll.snd;
            if (res.size()!=0 && res.get(0).size()==level.size()){
                break;
            }
            String value = poll.fst;
            for (int i = 0; i < value.length(); i++) {
                String newWord = value.substring(0, i) + "*" + value.substring(i + 1);
                List<String> words = map.get(newWord);
                if (words==null){
                    continue;
                }
                for (String s : words) {
                    if (s.equals(endWord)) {
                        level.add(endWord);
                        res.add(new ArrayList<>(level));
                        level.remove(level.size()-1);
                        break;
                    }
                    if (!visited.contains(s)) {
                        visited.add(s);
                        level.add(s);
                        deque.offer(new Pair<>(s, new ArrayList<>(level)));
                        level.remove(level.size()-1);
                    }
                }
            }
        }
        return res;

    }

    public static void main(String[] args) {
        ArrayList<String> strings = CollUtil.newArrayList("hot", "dot", "dog", "lot", "log", "cog");
        new Question126().findLadders("hit","cog",strings);
    }
}

class Pair<T, R> {
    T fst;
    R snd;

    public Pair(T fst, R snd) {
        this.fst = fst;
        this.snd = snd;
    }
}
